/*
 * sort.c
 *
 *  Created on: 2020��1��3��
 *      Author: Administrator
 */

#include <stdio.h>
#include <stdlib.h>
#include "../../include/sort/sort.h"

void insert_sort(int* array, int length) {

	int j = 0;
	for (int i = 1; i <= length-1; ++i) { // 执行n-1趟

		int temp = array[i]; // 监视哨
		for (j = i-1; j >= 0 ; j--) { // 寻找插入位置
			if (temp < array[j])
				array[j+1] = array[j]; // 后移
			else
				break;       // 找到位置
		}
		array[j+1] = temp;   // 插入
	}
}

void bin_insert_sort(int* array, int length) {

	int mid, low, high;
	for (int i = 1; i < length; ++i) {
		// 折半法找到插入位置
		int temp = array[i];    // 监视哨
		low = 0, high = i-1;
		while (low <= high) {
			mid = (low + high) / 2;
			if (low == high)
				break;          // 找到位置mid
			else if (temp < array[mid])
				high = mid - 1;
			else
				low = mid + 1;
		}
		// 移动
		for (int j = i-1; j >= mid; --j)
			array[j+1] = array[j];
		// 插入
		if (mid == 0)
			array[mid] = temp;
		else
			array[mid+1] = temp;
	}
}

void bubble_sort(int* array, int length) {

	for (int i = 1; i <= length-1; i++) { // 执行n-1趟

		int end = length - i - 1;    // 每一趟确定一个最大的元素
		for (int j = 0; j <= end; j++) {
			if (array[j] > array[j+1]) {  // 小元素前移
				int temp = array[j+1];    // 交换
				array[j+1] = array[j];
				array[j] = temp;
			}
		}
	}
}

void quick_sort(int* array, int low, int high) {

	int pivotloc;

	if (low < high) {
		pivotloc = partition(array, low, high); // 已经确定pivotloc位置
		quick_sort(array, low, pivotloc-1);
		quick_sort(array, pivotloc+1, high);
	}
}

int partition(int* array, int low, int high) {

	int temp = array[low]; // 低位第一个元素作为基准

	while (low < high) {
		while (low < high && array[high] >= temp)
			high--;
		array[low] = array[high];   // 遇到高位小元素时，放置低位
		while (low < high && array[low] <= temp)
			low++;
		array[high] = array[low];   // 遇到低位大元素时，放置高位
	}
	// 当low == high时
	array[low] = temp; // 放置基准
	return low;
}
/**
 * select sort(increased)
 * for every ith loop, select the minimun value in the array,
 * then swap minimun value with ith value.
 */
void select_sort(int* array, int length) {

	for (int i = 0; i < length; ++i) {
		int index = i; // 保存最小值下标

		for (int j = i+1; j < length; ++j) {
			if (array[j] < array[index])
				index = j;  // 若找到更小的值，更新index
		}
		// 交换
		int temp = array[i];
		array[i] = array[index];
		array[index] = temp;
	}
}

void merge_sort(int* array, int length) {

	int low = 0;
	int high = length-1;
	m_sort(array, low, high);
}

void m_sort(int* array, int low, int high) {

	if (low >= high) return;
	else {
		int mid = (low + high) / 2;
		m_sort(array, low, mid);
		m_sort(array, mid+1, high);
		merge(array, low, mid, high);
	}
}

void merge(int* array, int low, int mid, int high) {

	int length = high - low + 1;
	int* temp = (int*)malloc(sizeof(int)*length);
	int i = low;
	int j = mid+1;
	int k = 0; // 指示临时数组temp下标

	while (i <= mid && j<= high) {  // 两数组合并
		if (array[i] < array[j]) {
			temp[k] = array[i];
			i++;
			k++;
		} else {
			temp[k] = array[j];
			j++;
			k++;
		}
	}

	if (i > mid) {  // 如果A数组已存完
		while (j <= high) {
			temp[k] = array[j];
			j++;
			k++;
		}
	}
	if (j > high) { // 如果B数组已存完
		while (i <= mid) {
			temp[k] = array[i];
			i++;
			k++;
		}
	}

	for (int q = 0; q < length; ++q) {
		array[low+q] = temp[q];
	}

}
